ABC160 D - Line++
https://atcoder.jp/contests/abc160/tasks/abc160_d
提出
code: python
n, x, y = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
if (i == 1):
graph1.append(2)
elif (i == n+1):
graphn+1.append(n)
else:
graphi.append(i-1)
graphi.append(i+1)
graphx.append(y)
graphy.append(x)
print(graph)
# BFS
for i in range(1, n + 1):
for j in range(len(graphi)):
print(graphij)
解答
code: python
from collections import deque
n, x, y = map(int, input().split())
paths = [[] for _ in range(n+1)]
for i in range(1, n):
pathsi.append(i+1)
pathsi+1.append(i)
pathsx.append(y)
pathsy.append(x)
print(paths)
# ], 2, 1, 3, 4, 2, 4, 3, 5, 2, [4
# 最短距離ごとの組み合わせ数を探索の際に数えていく
# resultx: 最短距離 x の組み合わせ数
result = 0 * n
# 開始地点 (1 ~ n) を全部試す
for start in range(1, n+1):
# 距離をリセット
dist = -1 * (n+1)
# 開始地点を0にしてリセット
diststart = 0
queue = deque(start)
while queue:
now = queue.popleft()
# 現地点から行ける点
for nxt in pathsnow:
# すでに通った
if distnxt != -1:
continue
# 最短距離
distnxt = distnow + 1
queue.append(nxt)
# 距離が確定した際、result で数えておく
result[distnxt] += 1
# print(result)
# 0, 10, 8, 2, 0
# 往復で数えているので、2 で割って出力
for r in result1::
print(r//2)
テーマ
#bfs #graph
メモ
AtCoder Beginner Contest 160 D – Line++ をPython3で解く
提出
code: python
import queue
from collections import defaultdict
n, x, y = list(map(int, input().split()))
# 法則はあるか
graph = defaultdict(set)
for i in range(1, n):
graphi.add(i+1)
graphi+1.add(i)
graphx.add(y)
graphy.add(x)
print(graph)
# 重複 どう調べていく
ans = 0 * (n-1)
for i in range(1, n):
q = queue.Queue()
q.put(graphi)
while q:
for next in q:
解答
code: python
n, x, y = map(int, input().split())
ans = 0 * n
for i in range(1, n+1):
for j in range(i+1, n+1):
# X -> Yルートを使わない
k = j-i
# X -> Yルートを使う
l = abs(x - i) + abs(y - j) + 1
ansmin(k, l) += 1
for i in range(1, n):
print(ansi)
メモ
https://blog.hamayanhamayan.com/entry/2020/03/29/000745